package com.sheng.leetcode.year2023.month05.day18;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author liusheng
 * @date 2023/05/18
 * <p>
 * 1073. 负二进制数相加<p>
 * <p>
 * 给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。<p>
 * 数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。<p>
 * 例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。<p>
 * 数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。<p>
 * 返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。<p>
 * <p>
 * 示例 1：<p>
 * 输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]<p>
 * 输出：[1,0,0,0,0]<p>
 * 解释：arr1 表示 11，arr2 表示 5，输出表示 16 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：arr1 = [0], arr2 = [0]<p>
 * 输出：[0]<p>
 * <p>
 * 示例 3：<p>
 * 输入：arr1 = [0], arr2 = [1]<p>
 * 输出：[1]<p>
 * <p>
 * 提示：<p>
 * 1 <= arr1.length, arr2.length <= 1000<p>
 * arr1[i] 和 arr2[i] 都是 0 或 1<p>
 * arr1 和 arr2 都没有前导0<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/adding-two-negabinary-numbers">1073. 负二进制数相加</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1073 {

    @Test
    public void test01() {
//        int[] arr1 = {1, 1, 1, 1, 1}, arr2 = {1, 0, 1};
//        int[] arr1 = {0}, arr2 = {0};
//        int[] arr1 = {0}, arr2 = {1};
//        int[] arr1 = {0}, arr2 = {1, 0};
        int[] arr1 = {0}, arr2 = {1, 1};
        System.out.println(Arrays.toString(new Solution().addNegabinary(arr1, arr2)));
    }
}

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1, j = arr2.length - 1;
        List<Integer> ans = new ArrayList<>();
        // 从最低位开始遍历两个数组
        for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
            // arr1 数组的当前位数字
            int a = i < 0 ? 0 : arr1[i];
            // arr2 数组的当前位数字
            int b = j < 0 ? 0 : arr2[j];
            // 进位为 c，三个数相加的结果为 x
            int x = a + b + c;
            // 先将 c 置为 0
            c = 0;
            // 如果 x 减去 2，并向高位进位 -1，即逢 2 进 -1
            if (x >= 2) {
                x -= 2;
                c -= 1;
            } else if (x == -1) {
                // 如果 x == -1，由于 -(-2)^i = (-2)^ + (-2)^(i + 1)，所以我们可以将 x 置为 1，并向高位进位 1
                x = 1;
                c += 1;
            }
            // 将 x 加入答案数组中
            ans.add(x);
        }
        // 遍历结束后去除末尾的 0
        while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }
        // 并将数组反转即可
        Collections.reverse(ans);
        return ans.stream().mapToInt(x -> x).toArray();
    }
}

//作者：lcbin
//链接：https://leetcode.cn/problems/adding-two-negabinary-numbers/solution/python3javacgotypescript-yi-ti-yi-jie-mo-mg0a/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 超出最大范围
//class Solution {
//    public static String toNegabinary(long decimal) {
//        if (decimal == 0) {
//            return "0";
//        }
//        String negabinary = "";
//        while (decimal != 0) {
//            long remainder = decimal % -2;
//            decimal /= -2;
//            if (remainder < 0) {
//                remainder += 2;
//                decimal += 1;
//            }
//            negabinary = remainder + negabinary;
//        }
//        return negabinary;
//    }
//
//    public int[] addNegabinary(int[] arr1, int[] arr2) {
//        long sum = 0;
//        for (int i = arr1.length - 1; i >= 0; i--) {
//            if (arr1[arr1.length - 1 - i] == 1) {
//                sum += Math.pow(-2, i);
//            }
//        }
//        for (int i = arr2.length - 1; i >= 0; i--) {
//            if (arr2[arr2.length - 1 - i] == 1) {
//                sum += Math.pow(-2, i);
//            }
//        }
//        String s = Solution.toNegabinary(sum);
//        String[] split = s.split("");
//        int[] ans = new int[split.length];
//        for (int i = 0; i < split.length; i++) {
//            ans[i] = Integer.parseInt(split[i]);
//        }
//        return ans;
//    }
//}
